using System;
using System.IO;					// Zur Arbeit mit Datei
using System.Collections.Generic;

namespace GraphSpace
{
	public class Eulerkreis
	{

		private bool hatEulerkreis;	
		private List<Knoten> kreis;
		
		public Eulerkreis ()
		{
			hatEulerkreis = false;
			kreis = new List<Knoten>();
		}
	
		public void sucheEuler(oldGraph G)
		{
			bool trivialerCheck = true;			// wird false, wenn triviale Prüfung auf Knotengrad fehlschlägt
			
			foreach(Knoten v in G.V)
			{
				if(G.A[v.Id].Count != G.Ar[v.Id].Count)		// Prüfe ob Anzahl ein- und ausgehender Kanten gleich ist
				{
					// Wenn ungleich -> Graph kann keinen Eulerkreis enthalten
					trivialerCheck = false;		// triviale Überprüfung fehlgeschlagen
					break;						// Brich Überprüfung der Knotengrade ab
				}
			}
			
			if(trivialerCheck && G.V.Count>0)		// triviale Überprüfung standgehalten und es gibt Knoten mit ausgehenden Kanten
			{
				// Liste der Kanten kopieren (der Algo zerstört diese)
				Dictionary<int, List<Kante>> A = new Dictionary<int, List<Kante>>(G.A);
				kreis = EULER(G, A, G.V[0]);	// Hilfsfunktion auf Knoten-, Kantenmenge und Startknoten von G
				hatEulerkreis = true;
				//new List<Knoten>(G.V.Values)
			}
			
		}
		
		// Hilfsfunktion, siehe Folie 35
		private List<Knoten> EULER(oldGraph G, Dictionary<int, List<Kante>> E, Knoten v)
		{
			//Console.WriteLine("\tW mit v = "+v.Id + " und |E| = "+E.Count);
			List<Knoten> W = new List<Knoten>();
			W.Add(v);
			Knoten x = v;

			// Hauptkreis bestimmen
			while(E[x.Id].Count != 0)
			{
				//Console.WriteLine("\t\t" + x.Id + " x.|E|" + E[x.Id].Count);
				Kante e = E[x.Id][0];				// eine von x augehende Kante
				W.Add(e.Vnach);						// neues Ziel im vorl. Eulerkreis vermerken
				E[x.Id].RemoveAt(0);				// Kante e aus E entfernen
				x = e.Vnach;						// neues x festlegen
			}
			
			// Teilkreise der verbleibenden Kanten bestimmen
			Dictionary<int, List<Knoten>> Wi = new Dictionary<int, List<Knoten>>();
			for(int i =0; i<W.Count-1; i++)
				if(E[W[i].Id].Count>0)					// Gibt es in einem Knoten i des vorl. Eulerkreises noch unbesuchte Kanten
				{
					Wi[i] = EULER(G, E, W[i]);		// Kreis mit noch unbesuchten Kanten an Knoten i bestimmen
				}
			
			// Teilkreise hinzufügen
			foreach(var pair in Wi)
			{
				// Alle Elemente des Teilkreises, außer dem letzen, in den Hauptkreis einfügen
				W.InsertRange(pair.Key, pair.Value.GetRange(0,pair.Value.Count-1));
			}
						
			return W;
		}
		
		public bool speicherKreis(string pfad)
		{
			try
			{
				// Datei einlesen
				StreamWriter writer = new StreamWriter(pfad);
				if(hatEulerkreis)
					writer.WriteLine("1");
				else
					writer.WriteLine("0");
					
				foreach(Knoten w in kreis)
					writer.WriteLine(w.Id);
				
				writer.Close();
				return true;
			}
			catch
			{
				return false;
			}	
		}
		
		public bool HatEulerkreis
		{
			get{return this.hatEulerkreis;}
		}
		public List<Knoten> Kreis
		{
			get{return this.kreis;}
		}
	}
}
